/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ ∧IMORE ON NON-MONOTONIC REASONING

␈↓ α∧␈↓␈↓ αTThese␈α⊂notes␈α⊃supplement␈α⊂my␈α⊂␈↓↓Circumscription␈α⊃-␈α⊂A␈α⊂Form␈α⊃of␈α⊂Non-Monotonic␈α⊃Reasoning␈↓␈α⊂in
␈↓ α∧␈↓press in ␈↓↓Artificial Intelligence␈↓ and printed as Stanford Artificial Intelligence Memo AIM-334.

␈↓ α∧␈↓␈↓ αT1.␈α⊂Section␈α∂7␈α⊂-␈α⊂More␈α∂on␈α⊂Blocks␈α∂-␈α⊂axiomatizes␈α⊂the␈α∂conditions␈α⊂for␈α∂moving␈α⊂one␈α⊂block␈α∂onto
␈↓ α∧␈↓another.␈α
 That␈α∞formalization␈α
reifies␈α
(introduces␈α∞as␈α
individuals␈α
of␈α∞the␈α
domain)␈α
"things"␈α∞that␈α
may
␈↓ α∧␈↓prevent␈α∂the␈α∂action.␈α∂ This␈α∞reification␈α∂is␈α∂unnecessary␈α∂(though␈α∞it␈α∂is␈α∂may␈α∂be␈α∞useful),␈α∂and␈α∂we␈α∂get␈α∞a
␈↓ α∧␈↓somewhat neater formulation by replacing equation (22) of that section by

␈↓ α∧␈↓1)␈↓ αt ␈↓↓∀x y s.(doable(move(x,y),s) ⊃ on(x,y,result(move(x,y),s)))␈↓,

␈↓ α∧␈↓where␈α∂we␈α∂have␈α∂combined␈α∂all␈α∂the␈α∂conditions␈α∂for␈α∂performing␈α∂an␈α∂action␈α∂into␈α∂the␈α∂notion␈α∂that␈α∂the
␈↓ α∧␈↓action␈α∞is␈α∞␈↓↓doable␈↓␈α∞in␈α∞a␈α
situation.␈α∞ We␈α∞can␈α∞write␈α∞a␈α∞general␈α
statement␈α∞that␈α∞an␈α∞action␈α∞has␈α∞its␈α
normal
␈↓ α∧␈↓consequence provided it is doable in the form

␈↓ α∧␈↓2)␈↓ αt ␈↓↓∀action s.(doable(action,s) ⊃ conseq(action,result(action,s)))␈↓

␈↓ α∧␈↓and specialize it to the case at hand by writing

␈↓ α∧␈↓3)␈↓ αt ␈↓↓∀x y s'.(conseq(move(x,y),s') ≡ on(x,y,s'))␈↓.

␈↓ α∧␈↓␈↓ αTWe further have

␈↓ α∧␈↓4)␈↓ αt ␈↓↓∀x y s.(tooheavy(x,s) ⊃ ¬doable(move(x,y),s))␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓5)␈↓ αt ␈↓↓∀x y s.(¬clear(y,s) ⊃ ¬doable(move(x,y),s))␈↓.

␈↓ α∧␈↓Circumscribing ␈↓↓¬doable␈↓ in (4)∧(5) gives

␈↓ α∧␈↓6)␈↓ αt ␈↓↓∀x y s.(doable(move(x,y),s) ≡ ¬tooheavy(x,s) ∧ clear(y,s))␈↓.

␈↓ α∧␈↓The␈α
axioms␈α
for␈α
actions␈α
usually␈α
given␈α
in␈α
AI␈α
formulations␈α
can␈α
be␈α
regarded␈α
as␈α
obtained␈α
by␈αthis␈α
kind
␈↓ α∧␈↓of␈α
circumscription␈α
from␈αthe␈α
more␈α
open-ended␈α
subjective␈αformulations␈α
of␈α
common␈αsense␈α
knowledge
␈↓ α∧␈↓whose␈α
listings␈α
of␈α
what␈α∞can␈α
prevent␈α
an␈α
action␈α
are␈α∞subjectively␈α
recognized␈α
to␈α
be␈α∞incomplete.␈α
 The
␈↓ α∧␈↓circumscriptions␈αare␈αdone␈αnaively␈α
by␈αthe␈αresearcher␈αwhen␈αhe␈α
has␈αto␈αwrite␈αaxioms␈αgiving␈α
sufficient
␈↓ α∧␈↓conditions for actions.

␈↓ α∧␈↓␈↓ αTThis is still insufficient reification to permit statements about when one should circumscribe.

␈↓ α∧␈↓␈↓ αT2.␈αWhat␈αare␈αthe␈αreasoning␈αprocesses␈αthat␈αgo␈αto␈αthe␈αAmarel␈αrepresentation␈αof␈αM␈αand␈αC␈αor␈αto
␈↓ α∧␈↓a␈α∂similarly␈α∞simple␈α∂representation␈α∞of␈α∂a␈α∞concrete␈α∂set␈α∞of␈α∂blocks␈α∞on␈α∂a␈α∞table?␈α∂ The␈α∞model␈α∂should␈α∞be
␈↓ α∧␈↓somehow␈α
"constructible"␈αby␈α
the␈αreasoning␈α
program␈αonce␈α
we␈αhave␈α
decided␈αwhat␈α
facts␈αto␈α
take␈αinto
␈↓ α∧␈↓account.  A crucial step seems to be the mental act

␈↓ α∧␈↓␈↓ αT"Let␈α∞the␈α∞triplet␈α∞(m,c,b)␈α
be␈α∞the␈α∞numbers␈α∞of␈α∞missionaries,␈α
cannibals␈α∞and␈α∞boats␈α∞on␈α∞the␈α
initial
␈↓ α∧␈↓bank of the river in a given situation".
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓␈↓ αT3.␈αWhat␈α
is␈αthe␈α
relation␈αbetween␈αcircumscription␈α
and␈αprinciples␈α
of␈αsimplicity␈α
and␈αOckham's
␈↓ α∧␈↓razor and all of these to ␈↓↓ceteris paribus␈↓?

␈↓ α∧␈↓␈↓ αT4.␈αCircumscriptions␈α
are␈αmade␈αby␈α
minimizing␈αpredicates.␈α Are␈α
there␈αcorresponding␈α
rules␈αfor
␈↓ α∧␈↓generating Reiter or McDermott defaults?

␈↓ α∧␈↓␈↓ αT5. More on the propositional case.

␈↓ α∧␈↓␈↓ αTIt␈α
is␈α
informative␈αto␈α
consider␈α
the␈α
general␈αform␈α
of␈α
a␈α
circumscription␈αof␈α
a␈α
propositional␈αletter␈α
␈↓↓p␈↓
␈↓ α∧␈↓in an axiom ␈↓↓A.␈↓ We can always write ␈↓↓A␈↓ in the form (essentially disjunctive normal form)

␈↓ α∧␈↓7)␈↓ αt ␈↓↓(a1 ⊃ p) ∧ (a2 ⊃ ¬p)␈↓

␈↓ α∧␈↓where ␈↓↓a1␈↓ and ␈↓↓a2␈↓ involve other propositional variables.  The circumscription is simply

␈↓ α∧␈↓␈↓ αT␈↓↓p ≡ a1␈↓.

␈↓ α∧␈↓Suppose␈α∞there␈α
is␈α∞another␈α
free␈α∞variable␈α
␈↓↓q,␈↓␈α∞and␈α
we␈α∞want␈α
to␈α∞adjust␈α
␈↓↓q␈↓␈α∞so␈α
as␈α∞to␈α
make␈α∞␈↓↓p␈↓␈α
as␈α∞false␈α
as
␈↓ α∧␈↓possible.  Then the axiom takes the form

␈↓ α∧␈↓␈↓ αT␈↓↓(a1∧q ∨ a2∧¬q ⊃ p) ∧ (a3∧q ∨ a4∧¬q ⊃ ¬p)␈↓,

␈↓ α∧␈↓and the result of circumscription is

␈↓ α∧␈↓␈↓ αT␈↓↓p ≡ a1∧a2␈↓.

␈↓ α∧␈↓␈↓ αTThe␈α∂next␈α∂simplest␈α∂case␈α∂is␈α∂when␈α∂␈↓↓p(x)␈↓␈α⊂is␈α∂a␈α∂unary␈α∂predicate.␈α∂ It␈α∂isn't␈α∂yet␈α∂clear␈α⊂whether␈α∂the
␈↓ α∧␈↓occurences of clauses like

␈↓ α∧␈↓␈↓ αT␈↓↓p(x) ∧ ¬p(y)␈↓

␈↓ α∧␈↓give trouble for circumscription - i.e. results not in accordance with intuition.

␈↓ α∧␈↓␈↓ αTAs␈α⊂for␈α⊂examples,␈α∂there␈α⊂seems␈α⊂to␈α∂be␈α⊂no␈α⊂problem␈α∂about␈α⊂obtaining␈α⊂the␈α⊂usual␈α∂S-expression
␈↓ α∧␈↓partial ordering by circumscribing < in the axiom

␈↓ α∧␈↓␈↓ αT␈↓↓∀xy.(x < x.y ∧ y < x.y) ∧ ∀xyz.(x < y ∧ y < z ⊃ x < z)␈↓

␈↓ α∧␈↓Looking at it from another point of view, we get the axiom schema of LISP induction.

␈↓ α∧␈↓Second␈αthought:␈αActually␈αthere␈αmay␈αbe␈αa␈αproblem␈αin␈αgetting␈αthe␈αordering.␈α Third␈αthought:␈αThere
␈↓ α∧␈↓is␈α
no␈α
problem.␈α
 We␈αneed␈α
only␈α
plug␈α
in␈αthe␈α
usual␈α
recursive␈α
definition␈αof␈α
the␈α
ordering␈α
and␈αshow␈α
that
␈↓ α∧␈↓it␈α
satisfies␈αthe␈α
schema.␈α Fourth␈α
thought:␈α
But␈αhow␈α
do␈αwe␈α
show␈α
that␈αit␈α
is␈αminimal?␈α
 Fifth␈αthought:␈α
It
␈↓ α∧␈↓looks␈αlike␈αthe␈αminimization␈αschema␈αfor␈αthe␈αprogram␈αwill␈αshow␈αthat␈αit␈αsatisfies␈αthe␈αcircumscription
␈↓ α∧␈↓schema.

␈↓ α∧␈↓␈↓ αT6. The axiom

␈↓ α∧␈↓8)␈↓ αt ␈↓↓∀x ∃y.(y > x) ∧ P(y))␈↓
␈↓ α∧␈↓␈↓ u3


␈↓ α∧␈↓leads␈αto␈αa␈αcontradictory␈αcircumscription␈αassuming␈αthat␈αthe␈αordering␈αis␈αirreflexive.␈α This␈αis␈αbecause
␈↓ α∧␈↓any␈α⊃predicate␈α⊃␈↓↓P␈↓␈α⊃satisfying␈α⊃(8)␈α⊃will␈α⊃be␈α⊃true␈α⊂for␈α⊃an␈α⊃infinite␈α⊃unbounded␈α⊃set␈α⊃of␈α⊃elements␈α⊃of␈α⊂the
␈↓ α∧␈↓domain,␈αbut␈α
it␈αcan␈α
be␈αmade␈αfalse␈α
at␈αany␈α
subset␈αand␈αremain␈α
a␈αsolution␈α
provided␈αwhat␈α
remains␈αis
␈↓ α∧␈↓unbounded.  Thus there is no minimal solution.  This is probably the paradigm example.